//这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, 
//lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。 
//
// 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 
//
// 返回你最多可以修读的课程数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
//输出：3
//解释：
//这里一共有 4 门课程，但是你最多可以修 3 门：
//首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
//第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
//第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
//第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。 
//
// 示例 2： 
//
// 
//输入：courses = [[1,2]]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：courses = [[3,2],[4,3]]
//输出：0
// 
//
// 
//
// 提示: 
//
// 
// 1 <= courses.length <= 10⁴ 
// 1 <= durationi, lastDayi <= 10⁴ 
// 
//
// Related Topics 贪心 数组 排序 堆（优先队列） 👍 458 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2023-09-11 10:09:40
 * @description 630.课程表 III
 */
public class CourseScheduleIii{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CourseScheduleIii().new Solution();
		 int[][] courses = {{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}};
		 int[][] courses1 = {{5,5}, {4,6}, {2,6}};

		 System.out.println(solution.scheduleCourse(courses1));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*courses[i] = [durationi, lastDayi] 表示
		 第 i 门课将会 持续 上 durationi 天课，
		 并且必须在不晚于 lastDayi 的时候完成*/
    public int scheduleCourse(int[][] courses) {
		PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->b.compareTo(a));
		// 使用Stream流和Lambda表达式对courses进行排序
		Arrays.sort(courses, Comparator.comparingInt(course -> course[1]));
		//把第一个课程的持续时间作为开始时间，
		int total=0;
		q.offer(0);
		for (int i=0;i<courses.length;i++) {
			//没有超过持续时间就加入
			if(total+courses[i][0]<=courses[i][1]){
				q.offer(courses[i][0]);
				total+=courses[i][0];
				//如果不能加入，找出持续时间最长的一个替换当前的
			}else {
				if(q.peek()>courses[i][0]){
					//减去之前的然后加入新的这个时间
					total-=q.poll()-courses[i][0];
					q.offer(courses[i][0]);
				}
			}
		}
		return q.size()-1;
	}
}
//leetcode submit region end(Prohibit modification and deletion)
}
